 //--------------------------------------------------------------
//
// Size Computation on graph
//
//                                      ripertl
//
//--------------------------------------------------------------

#include "global.h"

// returns in exits_tab a number size of exits. Those exits will
// be chosen far from the entrance node AND far enough from each
// other. The minimal distance between two exits can be set in
// changing the MINDIST macro. (0.55 is a default)

//#define DEBUG
//#define COLOR_NODES
#define MINDIST 0.55

#define START_BUBBLE_SIZE 0.8
#define REDUCE_BUBBLE_SIZE 0.5

struct dist_vertex{
  int v;
  float d;
};

int sort_dv(const void *a,const void *b){

  if(((struct dist_vertex *)a)->d > ((struct dist_vertex *)b)->d) return 1;
  if(((struct dist_vertex *)a)->d < ((struct dist_vertex *)b)->d) return -1;
  return 0;
}

// Recursive propagation to compute all the shortests paths from a node.
void rec_distance(igraph_t *graph, int node, float curdist, struct dist_vertex * dv){
  if(dv[node].v != -1 && dv[node].d < curdist) return; // Node has already been explored by a shorter path.
  curdist += getSize(*graph,node);
  dv[node].v = node;
  dv[node].d = curdist;

  // Now explore the neighbors.
  igraph_vs_t vs;
  igraph_vit_t iterator;

 #ifdef DEBUG
  //  printf("Setting distance %f for node %d\n",curdist,node);
 #endif

  igraph_vs_adj(&vs,node,IGRAPH_ALL);
  igraph_vit_create(graph, vs, &iterator);

  while(!IGRAPH_VIT_END(iterator)){

    // Recursive call.
    rec_distance(graph,IGRAPH_VIT_GET(iterator),curdist,dv);

    IGRAPH_VIT_NEXT(iterator);
  }
 
 igraph_vit_destroy(&iterator); 
}

int get_exits(igraph_t *graph, int start, int *exits_tab, int size)
{
  igraph_vs_t vsall;

  igraph_vit_t iterator;
  
  igraph_vs_all(&vsall);
  igraph_vit_create(graph, vsall, &iterator);

  int i = 0;
   
  float fsize = sizeevaluator2(*graph);
  float dist;
  
  int nbnodes = (int) sizeevaluator1(*graph);
 
  struct dist_vertex dv[nbnodes];
 
  // Initialise dv;
  int p;
  for(p = 0;p < nbnodes;p++){
    dv[p].v = -1;
  }

  rec_distance(graph,start,0.0,&dv[0]);

/*   while(!IGRAPH_VIT_END(iterator)) */
/*     { */
/*       vertex = IGRAPH_VIT_GET(iterator); */
      
/*       dist = sizeevaluator4(*graph, 0, vertex)/ fsize; */
            
/*       dv[vertex].v = vertex; */
/*       dv[vertex].d = dist; */
      
/*       IGRAPH_VIT_NEXT(iterator); */
/*     } */

  qsort(&dv[0],nbnodes,sizeof(struct dist_vertex),sort_dv);
  
  int j;
  int k;
  int test;

  igraph_vector_t vend;
  igraph_vector_init(&vend,1);

  igraph_vector_t vweights;
  igraph_vector_init(&vweights,edgenbr);
  igraph_vector_init_copy(&vweights, weights, edgenbr);
 
  for(j = nbnodes-1; j>=0; j--){
      
#ifdef DEBUG
    printf("Trying node %d:\n",dv[j].v);
#endif

    test = 1;
    // Test if node is far enough from the previous ones.
    for (k=0;k<i;k++){
      if(test && dv[j].v != -1){
	//igraph_vs_1(&vs, dv[j].v);
	igraph_vector_set(&vend,0,dv[j].v);
	dist = sizeevaluator4(graph,exits_tab[k],&vend,&vweights)/fsize;
	if(dist < MINDIST){
	  // Drop node
#ifdef DEBUG
	  printf("Dropping node %d not far enough from %d (%f)\n",dv[j].v,exits_tab[k],dist);
#endif
	  test = 0;
	}
      }
    }

    if(test && dv[j].d >= MINDIST){
#ifdef DEBUG
      printf("Adding vertex %d with dist %f (rank %d)\n",dv[j].v,dv[j].d,i);
#endif
      exits_tab[i] = dv[j].v;
      i++;
    }
    
    if(i == size) break;
  }

  // Fill in the exits tab
  while(i < size){
    exits_tab[i] = -1;
    i++;
  }

  return 0;
  
}

int no_more_valid(char *valids, int size){
  int i;
  for(i = 0; i < size;i++){
    if(valids[i]) return 0;
  }
#ifdef DEBUG
  printf("No more valid nodes to be exits\n");
#endif 
  return 1;
}

int get_exits_bubbles_rec(igraph_t *graph, int start, int *exits_tab, int size, float bblesize){

  int nbnodes = (int) sizeevaluator1(*graph);
  int result = 0;

  char is_valid[nbnodes]; 
  
  //Initialise is_valid
  int i;
  for(i = 0;i < nbnodes;i++){
    is_valid[i] = 1;
  }
  is_valid[start] = 0; // The entrance cannot be an exit.
  
  struct dist_vertex dv[nbnodes];
 
  // Initialise dv;
  for(i = 0;i < nbnodes;i++){
    dv[i].v = -1;
  }

  rec_distance(graph,start,0.0,&dv[0]); // Compute shortest paths from start
  
  // Sort them
  qsort(&dv[0],nbnodes,sizeof(struct dist_vertex),sort_dv);
  
  float bubble_size = dv[nbnodes-1].d * bblesize;
  
  // Invalidate all nodes which are too near from start.
  for(i = 0; dv[i].d < bubble_size;i++){
    is_valid[dv[i].v] = 0;
#ifdef DEBUG
    printf("Disabled node %d with distance %f from %d\n", dv[i].v, dv[i].d, start);
#endif

#ifdef COLOR_NODES
    igraph_cattribute_VAS_set(graph, "color", dv[i].v, "sienna1");
#endif
  }

#ifdef DEBUG
  printf("Disable nodes at distance < %f\n", bubble_size);
#endif

  struct dist_vertex dv_exit[nbnodes];
  float current_bubble;
  int node;
  int j;
  // Now find the exits.
  for(j = 0; j < size; j++){
    if(no_more_valid(is_valid, nbnodes)) break; // If no more nodes are valid, abort.
    
    node = dv[i + (rand()%(nbnodes - i))].v;

    // Reject if not valid, select another
    while(!is_valid[node]){
      node = dv[i + (rand()%(nbnodes - i))].v;
    }

#ifdef DEBUG
    printf("Selecting node %d\n",node);
#endif 

    // Now the node is valid. Add it to not valid nodes and perform proximity check
    is_valid[node] = 0;
    
    int k;
    // Reinitialise dv_exit;
    for(k = 0;k < nbnodes;k++){
      dv_exit[k].v = -1;
    }
    
    rec_distance(graph,node,0.0, &dv_exit[0]);
    qsort(&dv_exit[0],nbnodes,sizeof(struct dist_vertex),sort_dv);
    current_bubble = dv_exit[nbnodes - 1].d * bblesize;

    // Invalidate all nodes which are too near from node.
    for(k = 0; dv_exit[k].d < current_bubble;k++){
      is_valid[dv_exit[k].v] = 0;
#ifdef DEBUG
      printf("Disabled node %d with distance %f from %d\n", dv_exit[k].v, dv_exit[k].d, node);
#endif
    }

#ifdef DEBUG
    printf("Disable nodes at distance < %f\n", current_bubble);
#endif

    // Add exit to exits_tab
    exits_tab[j] = node;

  }
  
  // Fill in the exits tab
  while(j < size){
    exits_tab[j] = -1;
    result++;
    j++;
  }  
						     
  return result;
}

int get_exits_bubbles(igraph_t *graph, int start, int *exits_tab, int size){
  float bblesize = START_BUBBLE_SIZE;
  while(get_exits_bubbles_rec(graph, start, exits_tab, size, bblesize)){
    bblesize = bblesize * REDUCE_BUBBLE_SIZE;
  }

#ifdef DEBUG
  printf("Final bubble size : %f\n", bblesize);
#endif

  return 0;
}
